

#pragma once	

#include <stdio.h>
#include <semaphore.h>
#include "memory.h"
#include "release_memory.h"

extern int info[MAX_L];
extern int sum;
extern Buddy* p_tree;
extern void* base;
extern sem_t g_sem;

void release_memory( void *p )
{
    mem_header_t *pointer = (mem_header_t *)p;
    pointer = &pointer[-1];             // get the address of the header
	
	printf("Release the memory block with header address: %p\n", pointer);
	
    long unsigned int p_value = (long unsigned int) pointer;
    Buddy *node = (Buddy *)p_tree;
    Buddy *tree = p_tree;
    Buddy *rel_node = NULL;

    int one = 1;
	
    // find the tree node with manage info.
    int l = 0;
    int index = 0;           // for bit operation to index the node on a level
    
sem_wait(&g_sem);
    while (! rel_node) {
        if (p_value == (long unsigned int)node->p) {
            if (node->left ==NULL ) {
                if (node->right ==NULL) {
                    rel_node = node;
				    printf("found the node at level %d\n", l);	
                }
                else {	
sem_post(&g_sem);	
				    return;            // right occurpied, misrelease
				}
            }
            else {
			    
                node = node->left;
                l++;
                index = index<<1;
				
				printf("look left to level %d\n", l);
				//printf("the index is %d\n", index);
            }
        }
        else if (node->right !=NULL ) {
            if (p_value >= (long unsigned int)(node->right->p)) {
                node = node->right;
                l++;
                index = (index<<1) +1;
				printf("look right to level %d\n", l);
            }
            else { //if (p_value < (long unsigned int)(node->right->p)) {
                node = node->left;
                l++;
                index = index<<1;
            }
        }
        else {                  // right == NULL
            node = node->left;
            l++;
            index = index<<1;
        }	

    }

    int level_head;
    // modify the nodes to represent the release
    level_head = one<<l;
    rel_node->p = NULL;
    info[l]++;
    l--;

    // modify the parent nodes to represent the release, and merge the empty block
    while (l >=0 ) {
        if (index%2 == 0) {             // it is left node
            index = index/2;            // get the parent index in its level
            level_head = level_head/2;
            tree[level_head -1 +index].left = NULL;     // modify the parent node to mark the release of this node
			

			printf("Block [%d] has been released------------------\n", 2*(level_head -1 +index)+1);

			
            if (tree[level_head -1 +index].right == NULL) { //if the right node is also empty, merge them to a higher level.
                tree[level_head -1 +index].p = NULL;
				
                info[l]++;
				printf("The available node in level %d is now %d\n", l, info[l]);
            }
            else
                break;
                    
        }
        else {                          // it is right node
            index = index/2;
            level_head = level_head/2;
            tree[level_head -1 +index].right = NULL;
			printf("Block [%d] has been released------------------\n", 2*(level_head -1 +index)+2);
            if (tree[level_head -1 +index].left == NULL) {
                tree[level_head -1 +index].p = NULL;
	
                info[l]++;
				printf("The available node in level %d is now %d\n", l, info[l]);

            }
            else
                break;
        }

        l--;
    }

sem_post(&g_sem);	
return;
}




